Data compression techniques are useful to represent information as accurately as possible with a minimum number of bits in order to minimize the amount of data that must be stored or transmitted for use in a computer system. Typically, data to be compressed may represent various types of information, such as audio and video information. One of the means primarily used for compressing data is the removal of redundant information. At the same time, however, the remaining information must accurately represent the data that has been compressed.
Typically, the compression of data involves three steps. In a first step, the data is transformed in order to reduce its size and to separate detail. A wide variety of transformation techniques are currently in use. By way of example, a transformation technique such as a discrete cosine transform is commonly used. In a second step the data is quantized. That is, the data is scaled and truncated appropriately. Truncation is preferably used only to discard information having detail that is not required by the user of the data. For example, in an image to be compressed, if there are pixels that the human eye could not perceive in the resulting image, these pixels may be discarded. In a third step, the data remaining after the quantization step is bit encoded using a suitable entropy encoding technique. This entropy encoding step further compacts the data by efficiently representing the bits in the data. For example, redundant bits may be discarded. Any suitable entropy encoding technique may be used. By way of example, common entropy encoding techniques include Huffman, arithmetic, binary, run-length, LZ and LZW encoding.
Traditional data compression methods work on data defined on simple geometries. Typical geometries used in conventional compression methods include: the real line (e.g., audio), a rectangle (e.g., images), or a three-dimensional raster (e.g., video). However, these conventional data compression technologies are not suitable for compression of data defined on higher-dimensional or complex geometries such as spheres, general polygonal models, etc.
There are numerous examples of complex geometries for which it would be useful to develop an appropriate data compression technique. One example is Earth data compression. At the moment very large data sets of Earth elevation data exists. A typical example is the ETOPO5 data set. This data set represents topographic data over the entire Earth. The data gives the elevation (depth) of the Earth from sea level in meters at a resolution of 5 arc minutes at the equator. Even with powerful workstations, manipulating, storing, and transmitting such data sets can be quite expensive. Other examples of similar data sets are satellite views of the face of the Earth and planetary data.
Another example of a complex geometry that is useful for modeling information is the human head. Current video telephone technology takes advantage of the fact that one of the most common image types that is transmitted during video conferencing is images of human heads. One technique used to reduce the amount of information transmitted contemplates first transmitting a three-dimensional (3-D) model of a person's head and thereafter only transmitting information indicative of subsequent head movements. A data compression technique suitable for speeding up the transmission of the original 3-D head models would therefore be desirable. Other areas of application that use head models include animation and multimedia.
Another relevant application is the interactive multi-resolution viewing of complex data sets. When building an interactive viewer for complex manifolds, it would be desirable to only store and display the information needed by the user. For example, if the user needs a global view of the data, a low resolution approximation may be used. When the user focuses on a particular area, a higher level of detail can be loaded and displayed in real time. A further example is the interactive multi-resolution processing and editing of surfaces. A user might wish to change a global feature of a complex 3-D model while keeping the finer resolutions unchanged. On the other hand, a user may wish to edit the finer details while keeping the coarser levels unchanged. In other words, it is desirable to provide a facility for interactively building and editing complex 3-D models. Such techniques have applications in computer graphics and modeling.
While various techniques are available in the prior art for compression of the simple geometries, no unified technique currently exists for the compression of data defined on complex and/or higher dimensional geometries. Accordingly, the present invention seeks to provide such a technique.
In recent years the use of a mathematical construct referred to as wavelets to model complex data has become increasingly popular. The basic idea of wavelets and wavelet transforms were developed in the eighties. See I. Daubechies, "Ten Lectures on Wavelets," CBMS-NSF Regional Conf. Series in Appl. Math., Vol. 61, Society for Industrial and Applied Mathematics, 1992; S. G. Mallat, "Multiresolution Approximations and Wavelet Orthonormal Bases of L.sub.2 (R)", Trans. Amer. Math. Soc., 315(1):69-87, 1989; and Y. Meyer, "Ondelettes et Operateurs, I: Ondelettes, II: Operateurs de Calderon-Zygmund, III: (with R. Coifman), Operateurs multilineaires," Hermann, 1990. English translation of first volume, "Wavelets and Operators", is published by Cambridge University Press, 1993.
One definition of a wavelet is: "Wavelets are building blocks that can quickly decorrelate data." This sentence incorporates the three main features of wavelets. First of all, they are building blocks for general sets of functions. Mathematically it can be said that wavelets form a basis. This means that each element of a general class may be written in a stable way as a linear combination of the wavelets. Secondly, wavelets have the power to decorrelate smooth functions. This means that the representation of the data in terms of the wavelet coefficient is somehow more "compact" than the original representation. The entropy in the wavelet representation is smaller than in the original representation. The decorrelation power follows from the fact that the wavelets already in some way resemble the data to be represented. Many signals have both correlation in space and frequency. Indeed, samples that are spatially close are more correlated than ones far apart, and frequencies often occur in bands. Wavelets are also local in space and frequency. Finally, the wavelet representation of a data set can be found quickly. More precisely, one can switch between the original representation of the data and its wavelet representation in a time proportional to the size of the data. The fast decorrelation power of wavelets is one key to compression applications.
In general, wavelets are basis functions that represent a given function at multiple levels of detail. Due to their local support in both space and frequency, they are suited for the sparse approximations of functions. Locality in space follows from their compact support, while locality in frequency follows from their smoothness and vanishing moments. In the classic wavelet setting, i.e., on the real line, wavelets are defined as the dyadic translates and dilates of one particular, fixed function. They are typically built with the aid of a scaling function. Scaling functions and wavelets both satisfy refinement relations (or two scale relations). This means that a scaling function or wavelet at a certain level of resolution (j) can be written as a linear combination of scaling basis functions of the same shape but scaled at one level finer (level j+1).
Over the last decade wavelets have become an exceedingly powerful and flexible tool for computations and data reduction. They offer theoretical characterizations of smoothness, insights into the structure of functions and operators, and practical numerical tools that lead to faster computational algorithms. Examples of their use in computer graphics include surface and volume illumination computations, curve and surface modeling and animation, among others. Given the high computational demand in the quest for speed in computer graphics, the increasing exploitation of wavelets comes as no surprise. While these and other applications can benefit greatly from wavelet techniques, some of these applications can provide new challenges to the underlying wavelet technology. One such challenge is the transformation of data defined on complex manifolds. In general, an M-dimensional manifold is a space N such that each point in N has a neighborhood homeomorphic to an open ball in R to the M power. For example, a two-dimensional (2-D) spherical surface embedded in Euclidean three-dimensional (3-D) space is such that each small portion of the sphere appears to be the same as a small portion of Euclidean 2-D space (i.e., the plane). This fact caused some people to believe that the Earth was flat.
Classic wavelet constructions define the wavelet functions as dyadic translates and dilates of one fixed function: "the mother wavelet." See, for example, C. K. Chui, "An Introduction to Wavelets," Academic Press, 1992; A. Cohen, I. Daubechies, and J. Feauveau, "Bi-orthogonal Bases of Compactly Supported Wavelets," Comm. Pure Appl. Math., 45:485-560, 1992; and I. Daubechies, "Orthonormal bases of compactly supported wavelets," Comm. Pure Appl. Math,. 41:909-996, 1988. Because translation and dilation only make sense in a flat Euclidean space, these classical, or first generation wavelets cannot be used for the transformation of data defined on more complex manifolds. Therefore, one needs to consider the generalization to second generation wavelets. These are wavelets that are not necessarily the translates and dilates of one function, but that still enjoy all the powerful properties of first generation wavelets, namely basis properties, decorrelation power, and fast algorithms. In general, it can be said that most all of the widely used classical wavelets may be represented using second generation wavelets, and it is believed that all classical wavelets may be so represented. In other words, second generation wavelets are a superset of most all classical wavelets. Thus, the term "second generation wavelets" as used herein refers not only to the specific second generation wavelets described, but also to those classical wavelets that may be represented using second generation wavelets.
The basic philosophy behind second generation wavelets is to build wavelets with all desirable properties (localization, fast transform) adapted to much more general settings than the real line, e.g., wavelets on manifolds. In order to consider wavelets on a surface, one needs a construction of wavelets that are adapted to a measure on the surface. In the case of the real line (and classical constructions) the measure is dx, the usual translation invariant Lebesgue measure. For a sphere, the usual area measure can be denoted by dw, for example. Adaptive constructions rely on the realization that translation and dilation are not fundamental to obtain the wavelets with the desired properties. The notion that a basis function may be written as a finite linear combination of basis functions at a finer, more subdivided level, is maintained and forms the key behind the fast transform. The main difference with the classical wavelets is that the filter coefficients of second generation wavelets are not the same throughout, but can change locally to reflect the changing (non-translation invariant) nature of the surface and its measure.
Classical wavelets and the corresponding filters are constructed with the aid of the Fourier transform. The underlying reason is that translation and dilation become algebraic operations after the Fourier transform. In the setting of second generation wavelets, translation and dilation can no longer be used, and the Fourier transform cannot be used as a construction tool. An alternative construction is provided by the lifting scheme.
This new concept in the construction of wavelets, the lifting scheme, has been introduced recently. This concept is described in W. Sweldens, "The Lifting Scheme: A Custom-design Construction of Biorthogonal Wavelets", Technical Report 1994:7, Industrial Mathematics Initiative, Department of Mathematics, University of South Carolina, 1994, which is incorporated herein by reference in its entirety. This lifting scheme differs from the classical constructions in the sense that it does not need to use Fourier transforms. Therefore, it is an excellent tool for the construction of second generation wavelets. In one implementation, triangular subdivision is used to model a three-dimensional manifold, such as a sphere. Such a triangular subdivision of a sphere 200 is generally illustrated in FIG. 2a. In this figure the surface of sphere 200 has been subdivided into triangles in the form of a geodesic sphere. Shown is a triangle 210 that represents one of the many triangles on the surface of the sphere. Note that triangle 210 itself forms a part of a larger triangle that is represented by triangles 211, 210, 212 and 213. It should also be noted that triangle 210 itself may be further subdivided according to the same scheme.
While modeling techniques that utilize second generation wavelets to represent data on complex manifolds have proven useful, working with such data can be extremely difficult since the amount of data required for modeling can be extremely large, and presently, there are no suitable mechanisms for compressing such data. Accordingly, the development of a compression arrangement suitable for compressing such data would be highly desirable.